package com.wj.uf;

import java.util.Arrays;

/**
 * @author wen.jie
 * @date 2021/8/26 10:52
 * 并查集
 */
public class UF_Tree {

    private int[] eleAndGroup;

    private int count;

    public UF_Tree(int N) {
        this.count = N;
        this.eleAndGroup = new int[N];
        //初始化eleAndGroup中的元素及其所在的组的标识符
        for (int i = 0; i < eleAndGroup.length; i++)
            eleAndGroup[i] = i;
    }

    //分组的个数
    public int count() {
        return count;
    }

    //元素p所在分组的标识符
    public int find(int p) {
        while (true) {
            if(p == eleAndGroup[p]) {
                return p;
            }
            p = eleAndGroup[p];
        }
    }

    //判断并查集中元素p和元素q是否在同一个分组中
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    //把p元素所在分组和q元素所在分组合并
    public void union(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot) return;
        eleAndGroup[pRoot] = qRoot;
        count--;
    }

    public void print(){
        System.out.println(Arrays.toString(eleAndGroup));
    }

}
